noip模拟赛2017.7.11

模拟试题(三)

【试题概览】

题目名称 中位数 敲砖块 单词 邮递员送信
提交文件 median.* brike.* words.* post.*
输入文件 median.in brike.in words.in post.in
输出文件 median.out brike.out words.out post.out
时间限制 1s 1s 1s 1s
空间限制 128MB 128MB 128MB 128MB

中位数

【题目描述】

有一个长度为 N 的数列{A1,A2,…,AN}，这 N 个数字恰好是 1..N 的一个排列。你需要统计有多少个 子序列{Ai,Ai+1,…,Aj}满足：i<=j 且 j-i+1 为奇数，序列的中位数为 B。例如{5,1,3}的中位数为 3。

【输入格式】

第一行包含两个正整数 N 和 B。
第二行包含 N 个整数，第 i 个整数为 Ai.

【输出格式】

仅包含一个整数，为满足条件的子序列的个数。

【数据规模】

对于 30%的数据，满足 N<=100;
对于 60%的数据，满足 N<=1000;
对于 100%的数据，满足 N<=100000,1<=B<=N。

【输入样例】

7 4

5 7 2 4 3 1 6

【输出样例】

4

题解

第一题想了一个比n^2小那么一点的方法，奈何忘记判断边界，直接gg（md还有20分）。8020.！&￥#！正解直接用d[i]前缀和的形式统计i位置及以前比B大的数和比它小的数个数之差，然后如果在B位置后面存在一个位置j使d[j]==d[i],则说明在i~j这段区间中比B大的数与比B小的数相等，和一个合法区间。然后如何O(n)判断？就是桶排序的类似思想，打标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,b,a[100010],gre[100010],les[100010],num[100010],flag[200010];
int trs(int x){return x+100010;}
int main()
{
	freopen("median.in","r",stdin);
	freopen("median.out","w",stdout);
	int pos,ans=0;
	scanf("%d%d",&n,&b);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		gre[i]=gre[i-1],les[i]=les[i-1];
		if(a[i]>b)gre[i]++;
		if(a[i]<b)les[i]++;
		if(a[i]==b)pos=i;
		num[i]=gre[i]-les[i];
	}
	for(int i=0;i<=pos;i++)flag[trs(num[i])]++;
	for(int i=pos;i<=n;i++)ans+=flag[trs(num[i])];
	cout<<ans;
	return 0;
}
/*
7 4
7 2 4 3 6 5 1
*/

敲砖块

【题目描述】

在一个凹槽中放置了 N 层砖块，最上面的一层有 N 块砖，从上到下每层依次减少一块砖。每块砖 都有一个分值，敲掉这块砖就能得到相应的分值，如图所示
14 15 4 3 23
33 33 76 2
2 13 12
22 23
31
如果你想敲掉第 i 层的第 j 块砖的话，若 i=1，你可以直接敲掉它；若 i>1，则你必须先敲掉第 i-1 层的第 j 和第 j+1 块砖。
你现在可以敲掉最多 M 块砖，求得分最多能有多少。

【输入格式】

第一行有两个正整数 N 和 M；
接下来的 N 行，描述这 N 层砖块上的分值 A[i,j]，满足 0<=A[i,j]<=100。

【输出格式】

仅一行，包含一个整数，为最大的得分。

【数据规模】

对于 20%的数据，满足 1<=N<=10,1<=M<=30;
对于 100%的数据，满足 1<=N<=50,1<=M<=500。

【输入样例】

4 5

2 2 3 4

8 2 7

2 3

49

【输出样例】

19

题解（xjb算法）

幸亏今天的第二题苟住了，dp直接AC，但我想说一下cxy想的记忆化搜索（1.因为dp真的很烦，公式推错直接gg.2.记忆化搜索还比较好想）。我们每次只处理一列中的选择方案，假设敲i及其以上（其实i以上是必然会被敲）由于敲砖方式的限制，下一列的搜索是存在限制的，必须敲掉i-1块及以上，当然也可以敲下面的。既然这个清楚了就比较好完成代码了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define N 51
using namespace std;
int n,m,flag[N][N][(N*(N+1)/2)],dp[N][N][(N*(N+1)/2)],mp[N][N],sum[N][N];
int dfs(int lie,int p,int lft)
{
	int rtn=sum[lie][p];
	if(flag[lie][p][lft])return dp[lie][p][lft];
	flag[lie][p][lft]=1;
	if(2*lft<(p*(p+1)))return dp[lie][p][lft]=-1;
	if(lft<0)return dp[lie][p][lft]=-1;
	if(lie>n)return dp[lie][p][lft]=0;
	if(lft==0)return dp[lie][p][lft]=0;
	for(int i=p;i<=n-lie+1;i++)
	{
		int now=sum[lie][i];	
		int k=dfs(lie+1,max(i-1,0),lft-i);
		if(k==-1)break;
		rtn=max(now+k,rtn);
	}
	return dp[lie][p][lft]=rtn; 
	
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n-i+1;j++)
			scanf("%d",&mp[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			sum[i][j]=sum[i][j-1]+mp[j][i];
	printf("%d",dfs(1,0,m));
	return 0;
}

单词

【题目描述】

有 N 个单词和字符串 T，按字典顺序输出以字符串 T 为前缀的所有单词。

【输入格式】

第一行包含一个正整数 N；
接下来 N 行，每行一个单词，长度不超过 50；
最后一行包含字符串 T。

【输出格式】

按字典顺序升序输出答案。

【数据规模】

对于 60%的数据，满足 1<=N<=1000;
对于 100%的数据，满足 1<=N<=10000 且所有字符均为小写字母。

【输入样例】

6

na

no

ki

ki

ka

ku

k

【输出样例】

ka

ki

ki

ku

题解

  1. 很烦，string果然还是不能被接受。不过今天通过这道题也学到了，如果我们不便对于一个二维数组进行排序，我们可以间接通过对其下标的排序来完成。不过这道题的小技巧在于我们可以把要匹配的前缀也加入排列，然后再加入一个前缀后+’z’+1的一个串来保证会被派到最后一个，通过一开始的下标记录，我们可以完成对排序后的数组经行O(n)查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,cnt,l[10010],bh[10010];
char ch[10010][100]; 
bool cmp(int x,int y){
	int len=min(l[x],l[y]);
	for(int i=0;i<=len-1;i++)
	{
		if(ch[x][i]==ch[y][i])continue;
		return ch[x][i]<ch[y][i];
	}
	return l[x]<l[y];
}
int main()
{
	freopen("words.in","r",stdin);
	freopen("words.out","w",stdout);
	int pos;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%s",ch[i]),l[i]=strlen(ch[i]),bh[i]=i;
	scanf("%s",ch[0]);
	l[0]=strlen(ch[0]),bh[0]=0;
	for(int i=0;i<l[0];i++)
		ch[n+1][i]=ch[0][i]; 
	ch[n+1][l[0]]='z'+1,l[n+1]=l[0]+1,bh[n+1]=n+1;
	stable_sort(bh,bh+2+n,cmp);
	for(int i=0;i<=n+1;i++)if(bh[i]==0){pos=i;break;}
	for(int i=pos+1;i;i++){
		if(bh[i]==n+1)break;
		else printf("%s\n",ch[bh[i]]);
	}
	return 0;
}
/*
6
na
no
ki
ki
ka
ku
k
*/

邮递员送信

【题目描述】

有一个邮递员要送东西，邮局在结点 1。他总共要送 N-1 样东西，其目的地分别是 2-N。由于这个 城市的交通比较繁忙，因此所有的道路都是单行的，共有 M 条道路，通过每条道路需要一定的时间。 这个邮递员每次只能带一样东西。求送完这 N-1 样东西并且最终回到邮局最少需要多少时间。

【输入格式】

第一行包含一个正整数 N 和 M；
接下来有 M 行，每行三个正整数 U、V、W，表示该条道路为从 U 到 V 的，且通过这条道路需要 W 的时间。满足 1<=U,V<=N,1<=W<=100000，输入保证任意两点都能互相到达。

【输出格式】

包含一个整数，为最少需要的时间

【数据规模】

30%的数据，1<=N<=200;
100%的数据，1<=N<=1000，1<=M<=10000.

【输入样例】

注意：如果有这样的情况：（1109） （1102） （1101）以最小的 w=1 进行存储

5 10

2 3 5

1 5 5

3 5 6

1 2 8

1 3 8

5 3 4

4 1 8

4 5 3

3 5 6

5 4 2

【输出样例】

83

题解

题目真的很有病，明明说了边数不超过10000，结果来个80000的数据，也是没谁了。由于题目中的边是单向边，所以建个反向边跑一跑就完事了，代码写的丑是真的，后来改题的时候弄了半天，傻X出题人

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <queue>
#define LL long long
using namespace std;
int n,m,cnt,p[1010],edge[1010][1010],vis[1010];LL dis[1010];
struct node{
	int a,b,w,nt;
}e[10010],t[10010];
void add1(int x,int y,int w){
	cnt++;
	e[cnt].a=x,e[cnt].b=y,e[cnt].w=w;
	e[cnt].nt=p[x],p[x]=cnt;
}
void add2(int x,int y,int w){
	cnt++;
	t[cnt].a=x,t[cnt].b=y,t[cnt].w=w;
	t[cnt].nt=p[x],p[x]=cnt;
}
queue<int>q1,q2;
void spfa1(){
	for(int i=1;i<=n;i++)dis[i]=1e15;dis[1]=0;
	q1.push(1);vis[1]=1;
	while(!q1.empty()){
		int k=q1.front();q1.pop();vis[k]=0;
		for(int i=p[k];i;i=e[i].nt){
			int kk=e[i].b;
			if(dis[kk]>dis[k]+e[i].w){
				dis[kk]=dis[k]+e[i].w;
				if(!vis[kk]){
					vis[kk]=1;
					q1.push(kk);
				}
			}
		}
	}
}
void spfa2(){
	for(int i=1;i<=n;i++)dis[i]=1e15;dis[1]=0;
	q2.push(1);vis[1]=1;
	while(!q2.empty()){
		int k=q2.front();q2.pop();vis[k]=0;
		for(int i=p[k];i;i=t[i].nt){
			int kk=t[i].b;
			if(dis[kk]>dis[k]+t[i].w){
				dis[kk]=dis[k]+t[i].w;
				if(!vis[kk]){
					vis[kk]=1;
					q2.push(kk);
				}
			}
		}
	}
}
int main()
{
	freopen("post.in","r",stdin);
	freopen("post.out","w",stdout);
	LL ans=0;
	memset(edge,63,sizeof(edge));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		edge[x][y]=min(edge[x][y],z);
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(edge[i][j]<=100000&&i!=j)
				add1(i,j,edge[i][j]);
	spfa1();
	for(int i=2;i<=n;i++)
		ans+=dis[i];
		
	memset(p,0,sizeof(p)),cnt=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(edge[i][j]<=100000&&i!=j)
				add2(j,i,edge[i][j]);
	spfa2();
	for(int i=2;i<=n;i++)
		ans+=dis[i];
	printf("%lld\n",ans);
	return 0;
}
/*
5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6 
5 4 2
*/
*/

赏

×

纯属好玩

扫码支持
扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦

本文标题:noip模拟赛2017.7.11

文章作者:Tyw_ei

发布时间:2017年07月19日 - 21时39分

最后更新:2017年07月24日 - 20时19分

原始链接:https://dextertyw.github.io/2017/07/19/[noip模拟赛2017.7.11]/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 模拟试题(三)
    1. 1.1. 【试题概览】
  2. 2. 中位数
    1. 2.1. 【题目描述】
    2. 2.2. 【输入格式】
    3. 2.3. 【输出格式】
    4. 2.4. 【数据规模】
    5. 2.5. 【输入样例】
    6. 2.6. 【输出样例】
    7. 2.7. 题解
  3. 3. 敲砖块
    1. 3.1. 【题目描述】
    2. 3.2. 【输入格式】
    3. 3.3. 【输出格式】
    4. 3.4. 【数据规模】
    5. 3.5. 【输入样例】
    6. 3.6. 【输出样例】
    7. 3.7. 题解（xjb算法）
  4. 4. 单词
    1. 4.1. 【题目描述】
    2. 4.2. 【输入格式】
    3. 4.3. 【输出格式】
    4. 4.4. 【数据规模】
    5. 4.5. 【输入样例】
    6. 4.6. 【输出样例】
    7. 4.7. 题解
  5. 5. 邮递员送信
    1. 5.1. 【题目描述】
    2. 5.2. 【输入格式】
    3. 5.3. 【输出格式】
    4. 5.4. 【数据规模】
    5. 5.5. 【输入样例】
    6. 5.6. 【输出样例】
    7. 5.7. 题解
,